//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//  This file is part of the buola project (https://code.google.com/p/buola/).  //
//                                                                              //
//  Copyright(c) 2007-2012 Xavi Gratal                                          //
//  gratal AT gmail DOT com                                                     //
//                                                                              //
//  Buola is free software: you can redistribute it and/or modify               //
//  it under the terms of the GNU General Public License as published by        //
//  the Free Software Foundation, either version 3 of the License, or           //
//  (at your option) any later version.                                         //
//                                                                              //
//  Buola is distributed in the hope that it will be useful,                    //
//  but WITHOUT ANY WARRANTY; without even the implied warranty of              //
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               //
//  GNU General Public License for more details.                                //
//                                                                              //
//  You should have received a copy of the GNU General Public License           //
//  along with buola.  If not, see <http://www.gnu.org/licenses/>.              //
//                                                                              //
//////////////////////////////////////////////////////////////////////////////////

#include <buola/io/glob.h>
#include <buola/io/curi.h>
#include <stack>
#include <sys/stat.h>
#include <dirent.h>
#include <cstddef>
#include <fnmatch.h>
#include <buola/os/cuser.h>

namespace buola { namespace io {

bool glob_match(const std::string &pSrc,const std::string &pGlob)
{
    return (!fnmatch(pGlob.c_str(),pSrc.c_str(),0));
}

void expand_braces(const std::string &pPattern,std::vector<std::string> &pDst)
{
    pDst.push_back(pPattern);
    for(int w=0;w<pDst.size();w++)
    {
        std::stack<std::size_t> lOpening;
        std::vector<std::size_t> lCommas;
        std::size_t lLastWithCommas=std::string::npos;
        
        std::string &lW=pDst[w];
        
        bool lDone=false;
        for(std::size_t c=0;!lDone&&c<lW.size();c++)
        {
            switch(lW[c])
            {
            case '{':
                lOpening.push(c);
                break;
            case ',':
                if(!lOpening.empty())
                {
                    if(lLastWithCommas!=lOpening.top())
                    {
                        lLastWithCommas=lOpening.top();
                        lCommas.clear();
                    }
                    
                    lCommas.push_back(c);
                }
                break;
            case '}':
                if(!lOpening.empty())
                {
                    if(lLastWithCommas==lOpening.top())
                    {
                        lCommas.push_back(c);
                        int lF=lLastWithCommas+1;
                        std::string lOld=lW;
                        for(int i=0;i<lCommas.size();i++)
                        {
                            std::string lNew=lOld.substr(0,lLastWithCommas);
                            lNew+=lOld.substr(lF,lCommas[i]-lF);
                            lNew+=lOld.substr(c+1);
                            lF=lCommas[i]+1;
                            if(i==0)
                                pDst[w]=lNew;
                            else
                                pDst.insert(pDst.begin()+w+i,lNew);
                        }
                        w--;
                        lDone=true;
                    }            
                    else
                    {
                        lOpening.pop();
                    }
                }
                break;
            case '\\':
                c++;
            default:
                break;
            }
        }
    }
}

int expand_tilde(const std::string &pSrc,std::string &pDst)
{
    if(pSrc[0]=='~')
    {
        int c;
        for(c=1;c<pSrc.size();c++)
        {
            if(pSrc[c]=='\\')
            {
                c=-1;
                break;
            }
            else if(pSrc[c]=='/')
                break;
        }
        
        if(c<0) //something was escaped... ignore it
        {
            pDst=pSrc;
            return 0;
        }

        if(c==1)
        {
            pDst=io::get_home().Path()+pSrc.substr(c);
            return 1;
        }
        else
        {
            os::CUser lUser(pSrc.substr(1,c-1));
            if(!lUser)
            {
                pDst=pSrc;
                return 0;
            }
            pDst=lUser.Home()+pSrc.substr(c);
            return c;
        }
    }
    else
    {
        pDst=pSrc;
        return 0;
    }
}

void glob_unescape(const std::string &pSrc,std::string &pDst)
{
    pDst.clear();
    for(int i=0;i<pSrc.length();i++)
    {
        switch(pSrc[i])
        {
        case '\\':
            i++;
            if(i==pSrc.length()) break;
        default:
            pDst+=pSrc[i];
        }
    }
}

static bool check_entry(std::string &pName,const struct stat &pStat,EGlob pFlags)
{
    if(pFlags&GLOB_ONLYDIR)
    {
        if(!S_ISDIR(pStat.st_mode)) return false;
    }
    if(pFlags&GLOB_NODIR)
    {
        if(S_ISDIR(pStat.st_mode)) return false;
    }
    if(pFlags&GLOB_ONLYEXEC)
    {
        if(!(pStat.st_mode&(S_IXOTH|S_IXGRP|S_IXUSR))) return false;
    }
    if(pFlags&GLOB_MARKDIRS)
    {
        if(S_ISDIR(pStat.st_mode)) pName+="/";
    }
    
    return true;
}

void glob_in_dir(const std::string &pDir,const std::string &pPattern,EGlob pFlags,std::vector<std::string> &pResult)
{
    std::string lDir;
    if(pDir.empty())
        lDir="./";
    else if(pDir[pDir.length()-1]!='/')
        lDir=pDir+'/';
    else
        lDir=pDir;
        
    if(pFlags&GLOB_NOGLOB)
    {
        std::string lName;
        
        if(pFlags&GLOB_NOESCAPE)
            lName=pPattern;
        else
            glob_unescape(pPattern,lName);
        std::string lPath=lDir+lName;
        struct stat lStat;
        if(stat(lPath.c_str(),&lStat)!=0)
            return;
        
        if(!check_entry(lName,lStat,pFlags))
            return;
        
        pResult.push_back(lName);
    }
    else
    {
        DIR *lDIR=opendir(lDir.c_str());
        if(!lDIR) return;
        
        dirent lEntry;
        dirent *lPtr;

        while(true)
        {
            readdir_r(lDIR,&lEntry,&lPtr);
            if(!lPtr) break;
            
            std::string lName(lEntry.d_name);
            if(lName[0]=='.'&&!(pFlags&GLOB_MATCHPERIOD))
            {
                if(pPattern[0]!='.') continue;
            }
            if(!glob_match(lName,pPattern)) continue;
            
            if(pFlags&GLOB_MUSTCHECK)
            {
                if(lEntry.d_type==DT_UNKNOWN||lEntry.d_type==DT_LNK||pFlags&GLOB_FULLCHECK)
                {
                    std::string lPath=lDir+lName;

                    struct stat lStat;
                    if(stat(lPath.c_str(),&lStat)!=0)
                        continue;
                    
                    if(!check_entry(lName,lStat,pFlags))
                        continue;
                }
                else //fast check
                {
                    if(pFlags&GLOB_ONLYDIR&&lEntry.d_type!=DT_DIR)
                        continue;
                    if(pFlags&GLOB_NODIR&&lEntry.d_type==DT_DIR)
                        continue;
                    if(pFlags&GLOB_MARKDIRS&&lEntry.d_type==DT_DIR)
                        lName+="/";
                }
            }
            
            pResult.push_back(lName);
        }
        
        closedir(lDIR);
    }
}

static void extract_components(const std::string &pPattern,std::vector<std::string> &pComponents,
                               std::vector<EGlob> &pComponentFlags,bool &pAbsolute)
{
    pAbsolute=false;
    pComponents.clear();
    pComponentFlags.clear();
    
    EGlob lCurFlags=GLOB_NOESCAPE|GLOB_NOGLOB;
    int lBegin=0;
    
    for(int i=0;i<pPattern.size();i++)
    {
        switch(pPattern[i])
        {
        case '\\':
            if(i+1==pPattern.size())
                throw XArgument("wrong glob pattern (ends in \\)");
            if(pPattern[i+1]=='/'&&i!=0)
            {
                if(i==0)
                {
                    pAbsolute=true;
                }
                else if(i!=lBegin)
                {
                    pComponents.push_back(pPattern.substr(lBegin,i-lBegin));
                    pComponentFlags.push_back(lCurFlags);
                    lCurFlags=GLOB_NOESCAPE|GLOB_NOGLOB;
                }
                lBegin=i+2;
            }
            lCurFlags&=~GLOB_NOESCAPE;
            ++i;
            break;
        case '/':
            if(i==0) //ignore a slash in the beginning, but add it to the first word
            {
                pAbsolute=true;
            }
            else if(i!=lBegin) //ignore two slashes in a row
            {
                pComponents.push_back(pPattern.substr(lBegin,i-lBegin));
                pComponentFlags.push_back(lCurFlags);
                lCurFlags=GLOB_NOESCAPE|GLOB_NOGLOB;
            }
            lBegin=i+1;
            break;
        case '*':
        case '?':
        case '[':
            lCurFlags&=~GLOB_NOGLOB;
            break;
        default:
            break;
        }
    }
 
    if(lBegin!=pPattern.size())
    {
        pComponents.push_back(pPattern.substr(lBegin,pPattern.size()-lBegin));
        pComponentFlags.push_back(lCurFlags);
    }
    
}

void glob(const std::string &pPattern,EGlob pFlags,std::vector<std::string> &pResult)
{
    if(pPattern.empty()) return;
    
    if((pFlags&GLOB_BRACES)&&pPattern.find('{')!=std::string::npos)
    {
        std::vector<std::string> lExpanded;
        expand_braces(pPattern,lExpanded);
        
        for(auto i=lExpanded.begin();i!=lExpanded.end();++i)
            glob(*i,pFlags&~GLOB_BRACES,pResult);
        return;
    }

    if(pFlags&GLOB_TILDES&&pPattern[0]=='~')
    {
        std::string lExpanded;
        
        if(int lCount=expand_tilde(pPattern,lExpanded))
        {
            if(pFlags&GLOB_KEEPTILDE)
            {
                std::vector<std::string> lResult;
                int lCountExp=lCount+lExpanded.length()-pPattern.length();                
                
                glob_prefixed(lExpanded.substr(0,lCountExp),lExpanded.substr(lCountExp),pFlags&~GLOB_TILDES,lResult);
                if(lCount<pPattern.length()) lCount++;
                
                std::string lTildePrefix=pPattern.substr(0,lCount);
                
                for(int j=0;j<lResult.size();j++)
                {
                    pResult.push_back(lTildePrefix+lResult[j]);
                }
                return;
            }
            else
            {
                return glob(lExpanded,pFlags&~GLOB_TILDES,pResult);
            }
        }
    }

    std::vector<std::string> lComponents;
    std::vector<EGlob> lComponentFlags;
    bool lAbsolute;
    
    extract_components(pPattern,lComponents,lComponentFlags,lAbsolute);

    if(lComponents.empty()) return;

    std::vector<std::string> lPrevious;
    if(lAbsolute)
        lPrevious.push_back("/");
    else
        lPrevious.push_back("");
    
    for(int i=0;i<lComponents.size()-1;++i)
    {
        std::vector<std::string> lNew;

        EGlob lFlags=GLOB_ONLYDIR|lComponentFlags[i];
        if(pFlags&GLOB_MATCHPERIOD)
            lFlags|=GLOB_MATCHPERIOD;
        
        for(int j=0;j<lPrevious.size();j++)
        {
            std::vector<std::string> lList;
            glob_in_dir(lPrevious[j],lComponents[i],lFlags,lList);
            
            for(int k=0;k<lList.size();k++)
            {
                //don't include . or .. as part of the path, unless it is explicit
                if(lList[k][0]=='.')
                {
                    if(!(lFlags&GLOB_NOGLOB)&&(lList[k]=="."||lList[k]==".."))
                        continue;
                }
                
                lNew.push_back(lPrevious[j]+lList[k]+'/');
            }
        }
        
        swap(lNew,lPrevious);
    }
    
    {
        std::vector<std::string> lNew;
        
        EGlob lFlags=pFlags|lComponentFlags.back();
        
        for(int j=0;j<lPrevious.size();j++)
        {
            std::vector<std::string> lList;
            glob_in_dir(lPrevious[j],lComponents.back(),lFlags,lList);
            
            for(int k=0;k<lList.size();k++)
                pResult.push_back(lPrevious[j]+lList[k]);
        }
    }
    
    if(pFlags&GLOB_SORT)
    {
        std::sort(pResult.begin(),pResult.end());
    }
}

void glob_prefixed(const std::string &pPrefix,const std::string &pPattern,EGlob pFlags,std::vector<std::string> &pResult)
{
    if(pPrefix.empty()) return glob(pPattern,pFlags,pResult);
    if(pPattern.empty()) return;
    
    if((pFlags&GLOB_BRACES)&&pPattern.find('{')!=std::string::npos)
    {
        std::vector<std::string> lExpanded;
        expand_braces(pPattern,lExpanded);
        
        for(auto i=lExpanded.begin();i!=lExpanded.end();++i)
            glob_prefixed(pPrefix,*i,pFlags&~GLOB_BRACES,pResult);
        return;
    }

    if(pFlags&GLOB_TILDES&&pPrefix[0]=='~')
    {
        std::string lExpanded;
        if(expand_tilde(pPrefix,lExpanded))
            return glob_prefixed(lExpanded,pPattern,pFlags&~GLOB_TILDES,pResult);
    }

    std::vector<std::string> lComponents;
    std::vector<EGlob> lComponentFlags;
    bool lAbsolute;
    
    extract_components(pPattern,lComponents,lComponentFlags,lAbsolute);

    if(lComponents.empty()) return;

    std::vector<std::string> lPrevious;

    std::string lPrefix;
    glob_unescape(pPrefix,lPrefix);
    
    if(lPrefix[lPrefix.length()-1]!='/') lPrefix+='/';

    lPrevious.push_back(lPrefix);
    
    for(int i=0;i<lComponents.size()-1;++i)
    {
        std::vector<std::string> lNew;

        EGlob lFlags=GLOB_ONLYDIR|lComponentFlags[i];
        if(pFlags&GLOB_MATCHPERIOD)
            lFlags|=GLOB_MATCHPERIOD;
        
        for(int j=0;j<lPrevious.size();j++)
        {
            std::vector<std::string> lList;
            glob_in_dir(lPrevious[j],lComponents[i],lFlags,lList);
            
            for(int k=0;k<lList.size();k++)
            {
                //don't include . or .. as part of the path, unless it is explicit
                if(lList[k][0]=='.')
                {
                    if(!(lFlags&GLOB_NOGLOB)&&(lList[k]=="."||lList[k]==".."))
                        continue;
                }
                
                lNew.push_back(lPrevious[j]+lList[k]+'/');
            }
        }
        
        swap(lNew,lPrevious);
    }
    
    {
        std::vector<std::string> lNew;
        
        EGlob lFlags=pFlags|lComponentFlags.back();
        
        for(int j=0;j<lPrevious.size();j++)
        {
            std::vector<std::string> lList;
            glob_in_dir(lPrevious[j],lComponents.back(),lFlags,lList);
            std::string lPreviousWithoutPrefix=lPrevious[j].substr(lPrefix.length());
            
            for(int k=0;k<lList.size();k++)
                pResult.push_back(lPreviousWithoutPrefix+lList[k]);
        }
    }

    if(pFlags&GLOB_SORT)
    {
        std::sort(pResult.begin(),pResult.end());
    }
}

/*namespace io*/ } /*namespace buola*/ }
